package com.zhn;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class LowestCommonAncestor {
    //考虑通过递归对二叉树进行先序遍历，当遇到节点 ppp 或 qqq 时返回。
    // 从底至顶回溯，当节点 p,qp, qp,q 在节点 root 的异侧时
    // 节点 root 即为最近公共祖先，则向上返回 root 。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //当越过叶节点，则直接返回 null ；
        //当 root 等于 p,qp, qp,q ，则直接返回 root ；
        if(root == null || root == p|| root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}
